package com.zac.coroutine.algorithm.leetcode.tree

/**
 * author zac
 * date 2024/11/20
 * 二分搜索树
 *
 * 性质:
 *  1.节点可比较(实现comparable接口)
 *  2.左节点小于中节点小于右节点
 *
 */
class BST {

    data class Node(
        var value: Int,
        var leftNode: Node?,
        var rightNode: Node?,
    ) : Comparable<Node> {
        override fun compareTo(other: Node): Int {
            return value - other.value
        }

        override fun toString(): String {
            return value.toString()
        }

    }

    private var root: Node? = null


    fun add(node: Node) {
        root = insert(root, node)
    }

    private var size = 0

    fun size(): Int {
        return size
    }

    /**
     * 插入
     */
    private fun insert(root: Node?, node: Node): Node {
        if (root == null) {
            size++
            return node
        }

        if (root < node) {
            root.rightNode = insert(root.rightNode, node)
        }

        if (root > node) {
            root.leftNode = insert(root.leftNode, node)
        }
        return root
    }


    fun preOrder() {
        preOrderOpt(root)
    }

    fun inOrder() {
        inOrderOpt(root)
    }

    fun postOrder() {
        postOrderOpt(root)
    }

    /**
     * 前序遍历
     * 中左右
     */
    private fun preOrderOpt(node: Node?) {
        if (node == null) return
        println(node)
        preOrderOpt(node.leftNode)
        preOrderOpt(node.rightNode)
    }

    /**
     * 中序遍历
     * 左中右
     */
    private fun inOrderOpt(node: Node?) {
        if (node == null) return
        inOrderOpt(node.leftNode)
        println(node)
        inOrderOpt(node.rightNode)
    }

    /**
     * 后续遍历
     * 左右中
     */
    private fun postOrderOpt(node: Node?) {
        if (node == null) return
        postOrderOpt(node.leftNode)
        postOrderOpt(node.rightNode)
        println(node)
    }

}